/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

/**
 * <p>
 * 获得连续子数组的最大和
 *  For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray
 * [4,−1,2,1] has the largest sum = 6.
 * 
 * 
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月18日
 */
public class MaximumContiousSubarray {
    //思路1：分析数组规律，保存累加数字之和。如果累加和小于0，那么累加和等于当前数字；如果累加和大于0，累加。
    public int maxSubArray(int[] nums) {
        //数组为空
        if(nums==null){
            return -1;
        }
        int len = nums.length;
        int curSum = nums[0];
        int greatSum = nums[0];
        for(int i=1;i<len;i++){
            if(curSum<=0){
                curSum = nums[i];
            }else{
                curSum+=nums[i];
            }
            if(curSum>greatSum){
                greatSum = curSum;
            }
        }
        return greatSum;
    }
    public static void main(String[] args) {
        //[−2,1,−3,4,−1,2,1,−5,4]
//        int []arr = new int []{-2, 1,-3,4,-1,2,1,-5,4};
        int []arr = new int []{1,-2,3, 10,-4,7,2};
        MaximumContiousSubarray maximumContiousSubarray = new MaximumContiousSubarray();
        System.out.println("Max:"+maximumContiousSubarray.maxSubArray(arr));
    }
}
